package com.cheng.algorithm.search;

import java.util.ArrayList;

/**
 * @User Administrator
 * @Classname BinarySearch
 * @Project Data-structure-and-algorithm
 * @Description 二分查找功能完善：当一个数组中有多个相同值时，返回所有相同值的下标
 * 思路分析：
 * 1。在找到mid下标后,不要马上返回
 * 2。向mid的左边扫描，将所有满足 findVal 的元素的下标，加入到集合ArrayList
 * 3。向mid的右边扫描，将所有满足 findVal 的元素的下标，加入到集合ArrayList
 * 4。将Arraylist返回
 * @Author wpcheng
 * @Create 2021-08-16-9:41
 * @Version 1.0
 */
public class BinarySearchPlus {
    public static void main(String[] args) {
        int arr[] = {1, 8, 10, 89, 89, 89, 106, 256};
        ArrayList<Integer> list = binarySearch(arr, 0, arr.length - 1, 189);
        if (list.size() == 0){
            System.out.println("要查找的值不存在");
        }else {
            System.out.println("查找到下标为："+list+" 的数");
        }
    }
    /**
     *
     * @param arr       数组
     * @param left      左边的索引
     * @param right     右边的索引
     * @param findVal   要查找的数
     * @return  找到返回下标，没找到返回-1
     */
    public static ArrayList<Integer> binarySearch(int[] arr, int left, int right, int findVal){
        int mid = (left + right) / 2;
        int midVal = arr[mid];
        //当left> right,表明递归完整个数组，仍然没有找到findval，就需要退出递归
        if (left > right){
            return new ArrayList<Integer>();
        }
        //findval >arr[mid]，说明你要查找的数在mid的右边,因此需要递归的向右查找
        if (findVal > midVal){
            return binarySearch(arr,mid+1,right,findVal);
        //findval<arr[mid],说明你要查找的数在mid的左边,因此需要递归的向左查找
        }else if (findVal < midVal){
            return binarySearch(arr,left,mid-1,findVal);
        //findval == arr[mid]说明找到，就返回
        }else {
            ArrayList<Integer> list = new ArrayList<>();
            //向mid的左边扫描，将所有满足 findVal 的元素的下标，加入到集合ArrayList
            int temp = mid - 1;
            while (true){
                if (temp < 0 || arr[temp] != findVal){
                    break;
                }
                list.add(temp);
                temp--;
            }

            //向mid的右边扫描，将所有满足 findVal 的元素的下标，加入到集合ArrayList
            list.add(mid);
            temp = mid + 1;
            while (true){
                if (temp > arr.length-1 || arr[temp] != findVal){
                    break;
                }
                list.add(temp);
                temp++;
            }
            return list;
        }

    }


}
